import java.util.PriorityQueue;
import java.util.Queue;

/*
 * @lc app=leetcode.cn id=148 lang=java
 *
 * [148] 排序链表
 */

// @lc code=start



class Solution {

    
    public ListNode sortList(ListNode head) {
        if(head==null){
            return null;
        }
        Queue<ListNode> queue=new PriorityQueue<ListNode>((first,second)->(first.val-second.val));
        while(head!=null){
            queue.offer(head);
            head=head.next;
        }
        head=queue.poll();
        ListNode curr=head;
        while(!queue.isEmpty()){
            curr.next=queue.poll();
            curr=curr.next;
        }
        curr.next=null;
        return head;
    }
}
// @lc code=end

